This invention relates to coding of signals and, more specifically, to coding of signals with the aid of a vector codebook.
Because transmission capacity is often limited, the art of signal transmission relies very heavily on signal coding. In many situations, artisans code the information to compact or compress the information to be transmitted. In others, they code the information to simply send less than all of the provided information. The latter choice results in reception of less than a perfect replica of the provided information. Nevertheless, the reception of less than a perfect replica is often acceptable, because the ultimate recipient of the information either does not require the perfect replica, or can accept less than the perfect replica without detrimental defects. For example, a human listening to speech, or viewing an image, is capable of resolving a only limited amount of information. When the information presented to the subject contains more information than can be resolved, some information is simply not perceived. Hence, there is no useful purpose for sending more information than can be perceived. The same occurs with controlled systems, such robots, etc.
Recognizing that not all of the provided information needs to be sent to the receiver, artisans have concentrated their encoding efforts to minimize the error resulting from the loss of data. This error is the difference between the provided information and the information that the recipient, or information sink, can receive with the designed encoding approach.
In a copending application titled "Adaptive Non-Linear Quantizer", Ser. No. 07/626279, filed Dec. 11, 1990, a system for encoding video signals is disclosed. It is a rather complex arrangement where a TV image frame is encoded through a sequence of steps. First, the image frame is divided into segments and each segment is tested against the immediately previous TV image frame. The test develops a motion vector for each segment, which points to the area in the immediately previous image frame that best approximates the tested segment. Based on the developed motion vectors, an approximated current image frame is constructed from the previous image frame. Thereafter, the approximated current image frame is subtracted from the actual current image frame to develop a difference image frame. The difference image frame is then transformed to what might be considered a frequency domain, and the developed coefficients are encoded for transmission. In the course of the encoding process, coefficients are grouped into collections, and each collection is considered as a vector. Taking advantage of the fact that the collections have certain prevalent patterns of coefficient strengths, the amount of information to be transmitted is reduced by truncating some information and by chosing to restrict transmission to only a subset of the possible patterns. The task, in such an arrangement, is to select the best of the permissible patterns (that would be transmitted) to represent each of the actual patterns that ought to be transmitted.
The selection is carried out by maintaining the permissible patterns in a look-up table, which is commonly referred to as a vector codebook. To determine which of the permissible patterns can best represent a given pattern, each of the vector codebook entries is accessed and compared to the given pattern in accordance with some specified error criteria. The permissible pattern that yields the lowest error measure is selected for transmission. The typical error measuring criteria assesses the error contributed by each of the elements (the developed coefficients) of the selected permissible vector. The overall error is the sum of the errors created by the individual elements.
In devising hardware to perform this selection process, the designer can assess the error contributed by each of the elements either sequentially or in parallel. Parallel operation is much faster, but it requires a substantially larger amount of hardware. Serial operation requires much less hardware, but is much slower.
In the video encoding environment disclosed in the aforementioned application, the speed with which the best permissible codebook vector is identified needs to be high because the time allotted for this determination is very short. On the other hand, parallel operation is unattractive because the codebook vectors contain many elements; and in operation, more elements means more hardware.
It is an object of this invention, therefore, to devise a vector codebook arrangement that can determine the best selection of a permissible codebook vector, with a speed that approaches the speed of the parallel computation approach and with hardware size and complexity that approaches the serial computation approach.